package simple;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。
 * 如果不存在，则返回 -1 。
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class FirstUniqueCharacterInAString {
    /**
     * 两次遍历字符串，时间复杂度O(n)  空间复杂度O(n)
     * 速度 25ms
     * */
    class Solution {
        public int firstUniqChar(String s) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(map.containsKey(c)){
                    map.put(c, -1);
                }else{
                    map.put(c, i);
                }
            }

            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(map.containsKey(c) && map.get(c) != -1){
                    return map.get(c);
                }
            }
            return -1;
        }
    }

    /**
     * 遍历一次字符串即可。 速度提升到了16ms
     * */
    class Solution1 {
        public int firstUniqChar(String s) {
            int[] flag = new int[26];
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                flag[c - 'a']++;
                map.putIfAbsent(c, i);
            }

            int result = Integer.MAX_VALUE;
            for (int i = 0; i < 26; i++){
                if(flag[i] == 1){
                    result = Math.min(map.get((char) (i + 'a')), result);
                }
            }
            return result == Integer.MAX_VALUE ? -1 : result;
        }
    }

    /**
     * 网友的1ms 牛逼！
     * 利用Java的API
     * */
    class Solution2 {
        public int firstUniqChar(String s) {
            int res = s.length();
            for(char a = 'a'; a <= 'z'; a++){
                int ind = s.indexOf(a);
                if(ind != -1 && ind == s.lastIndexOf(a)){
                    res = Math.min(res, ind);
                }
            }
            return res == s.length() ? -1: res;
        }
    }
}
